
class Solution:
    def numWays(self, n: int) -> int:
        ans=[1]*100
        ans[1]=1
        ans[2]=2
        if n<3:
            return ans[n]
        else:
            for i in range(3,n+1):
                ans[i]=ans[i-1]+ans[i-2]
            return ans[n]


if __name__ == '__main__':
    s=Solution()
    for i in range(20):
        print(i,s.numWays(i))